package com.wcj.stack.dfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

/**
 * 给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
 *
 * 图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
 */

public class 克隆图 {
    private HashMap<Node,Node> visited = new HashMap<>();

    /**
     *DFS深度优先遍历
     * @param node
     * @return
     */
    public Node cloneGraph(Node node) {
        if (node == null){
            return node;
        }
        // 如果该结点已经被访问，直接从哈希表取出对应的克隆结点
        if (visited.containsKey(node)){
            return visited.get(node);
        }
        // 克隆结点，为了深拷贝，不会克隆它的邻居
        Node cloneNode = new Node(node.val,new ArrayList<>());
        visited.put(node,cloneNode);
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }

    /**
     * BFS广度优先遍历
     * @param node
     * @return
     */
    public Node cloneGraph2(Node node){
        if (node == null){
            return node;
        }
        HashMap<Node,Node> visited = new HashMap<>();
        //将结点添加到队列
        LinkedList<Node> queue = new LinkedList<>();
        visited.put(node,new Node(node.val,new ArrayList<>()));

        //广度优先遍历
        while (!queue.isEmpty()){
            //取出队列头结点
            Node n = queue.remove();
            for (Node neighbor : n.neighbors) {
                if (!visited.containsKey(neighbor)){
                    visited.put(neighbor,new Node(neighbor.val,new ArrayList<>()));
                    queue.add(neighbor);
                }
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }




















}
